/*
词典中最长的单词
class Solution {
    public String longestWord(String[] words) {
        //先将数组排序 按字符长度从小到大排序 当字符长度相等，按字符排序 大的在前排序 小的在后
        Arrays.sort(words,(a,b)-> {
            if(a.length() != b.length()) {
                return a.length()-b.length();
            }
            //当字符大小相等时候
            return b.compareTo(a);
        });

        //创建哈希表 判断当前字符串除去最后一个是否包含在哈希表中
        Set<String> hash = new HashSet<>();
        //最终结果ret
        String ret = "";
        hash.add(ret);
        //遍历words数组
        for(String word : words) {
            //拿出当前字符串除最后一个字符
            String s = word.substring(0,word.length()-1);
            //看看是否存在
            if(hash.contains(s)) {
                //更新结果
                ret = word;
                hash.add(word);
            }
        }
        return ret;
    }
}
重排链表
class Solution {
    public void reorderList(ListNode head) {
        // 先找到中间节点
        if (head == null || head.next == null || head.next.next == null) {
            return; // 如果链表为空或只有一个节点，直接返回
        }

        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //头插法
        ListNode newHead =new ListNode(0);
        ListNode cur = slow.next;
        slow.next = null;//分割
        //反转后半部分链表
        while(cur != null) {
            ListNode curN = cur.next;
            cur.next = newHead.next;
            newHead.next = cur;
            cur = curN;
        }
        //合并俩个链表 1->2->3   newhead->5->4->null
        ListNode cur2 = newHead.next;
        ListNode cur1 = head;
        ListNode ret =new ListNode(0);
        ListNode prev = ret;
        while(cur1 != null) {
            //先插入前半部分 prev -> 1
            prev.next = cur1;
            prev = cur1;
            cur1 = cur1.next;

            //再插入后半部分  1 ->5
            if(cur2 != null) {
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
    }
}
对称二叉树
class Solution {
    public boolean isSymmetric(TreeNode root) {
       if(root == null) return true;

       return dfs(root.left,root.right);
    }
    boolean dfs(TreeNode left, TreeNode right) {
        //终止条件
        if(left == null && right !=null || left != null && right == null) return false;
        if(left == null && right == null) return true;
        if(left.val != right.val) return false;
        //左子树左和右子树右比较  左子树的右和右子树的左比较
        return dfs(left.left,right.right) && dfs(left.right,right.left);
    }
}
二叉树的最大深度
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right)+1;
    }
}
 */